<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>归并排序</title>
  </head>
  <body>
    <script>
      /** 归并排序
       *
       * 工作原理：分治策略。
       *   + 划分阶段：不断从数组中心处分开，直到数组只有一个元素，终止划分
       *   + 合并阶段：将左右两个有序数组合并为一个数组，直到结束
       * 
       * 时间复杂度：O(nlogn)   空间复杂度：O(n)
       */


      let data = [6,5,7,4,8,3,9,2,0,1,10]
      function mergeSort(arrs) {
        const length = arrs.length;
        if(length <= 1) { // 拆分到数组只包含一个元素
          return arrs
        }
        const mid = Math.floor(length/2) // 计算中间位置
        const left = mergeSort(arrs.slice(0,mid)) // 递归实现 “分割”数组
        const right = mergeSort(arrs.slice(mid)) // 递归实现分割数组
        console.log('left____', left)
        console.log('right____', right)
        // 合并数组
        return merge(left, right)
      }

      function merge(left, right) {
        let i=0, j=0; // 定义两个指针，分别指向两个数组的开头
        let result = []; // 存放合并后的数组
        // 从左往右对比 left 和 right 的元素，按从小到大的顺序放入到 result 中
        while (i < left.length && j < right.length) {
          if(left[i] <= right[j]) {
            result.push(left[i])
            i++
          } else {
            result.push(right[j])
            j++
          }
        }
        // 将 left 剩余元素添加到  result 中
        while (i < left.length) {
          result.push(left[i])
          i++
        }
        // 将 right 剩余元素添加到 result
        while (j < right.length) {
          result.push(right[j])
          j++
        }
        console.log('合并后的数组 result: ', result)
        return result  // 返回合并后的数组
      }
      const sortedArr = mergeSort(data);
      // 打印结果
      console.log(data, ' ------归并排序------- ', sortedArr);
      document.write(data, ' ------归并排序------ ', sortedArr)
    </script>
  </body>
</html>
